package arrray;

/**
 * @author huangxianjin
 * @date 2025/8/14 22:47
 * @description "跳跃的游戏"
 */
public class LC_55 {
    //官方做法-贪心算法
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    //大佬做法1：
    /*
     * 1.如果所有元素都>=1，则可直接判断为true。因为我可以一次走一步，像一只乌龟一样走到终点。
     * 2.如果有元素为0，可以把0当作“坑”，为了不掉进坑里，我需要判断坑之前的位置，是否允许我一次跳多格，
     * 像一只兔子一样越过这个坑，如果可以越过这个坑，则继续往终点走，并继续判断未来的其他坑。
     * 如果我永远都无法越过某一个坑，则返回false，我将不可能到达终点。
     * */
    public boolean canJump2(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) { //不用考虑最后一个元素为0的情况
            if (nums[i] == 0) { //只关注0即可（由左向右）
                boolean flag = false;
                for (int j = 0; j < i; j++) { //判断之前的位置有位置可以越过该“坑”
                    if (nums[j] + j > i) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    return false;
                }
            }
        }
        return true;
    }

    //大佬做法2-你能越过后一个0，一定能越过前一个0，多个0在一起，我只记住最后一个。
    // flag表示能不能越过，k是0的下标
    public boolean canJump3(int[] nums) {
        boolean flag = true;
        int k = Integer.MAX_VALUE;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] == 0 && flag) {//由右向左
                k = i;
                flag = false;
            }
            if (nums[i] + i > k) {
                flag = true;
            }
        }
        return flag;
    }
}
